package com.mj.listen1._12_堆;

import com.mj.listen1._12_堆.heap.MaxBinaryHeap;
import com.mj.listen1._12_堆.heap.MinBinaryHeap;
import com.mj.listen1._12_堆.printer.BinaryTrees;

import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
//        test4();
        test5();
    }

    // topK问题
    private static void test5() {
        int k = 5;
        Integer[] arr = {15, 52, 2, 90, 59, 68, 25, 5, 13, 69, 12, 81, 10, 96, 16, 51, 56, 20, 42};
        MinBinaryHeap<Integer> heap = new MinBinaryHeap<>();
        for (int i = 0; i < arr.length; i++) {
            if (heap.size() < k) {// 前k个数添加到小顶堆。if (i < k)也行
                heap.add(arr[i]);
            } else if (arr[i] > heap.get()) {// 如果是第k + 1个数，并且大于堆顶元素
                heap.replace(arr[i]);
            }
        }
        BinaryTrees.print(heap);
    }

    /**
     * 使用大顶堆，实现小顶堆
     */
    private static void test4() {
        // 重写Comparator接口
        Integer[] arr = {15, 52, 2, 90, 59, 68, 25, 5, 13, 69, 12, 81, 10, 96, 16, 51, 56, 20, 42};
        MaxBinaryHeap<Integer> heap = new MaxBinaryHeap<>(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                // compare的返回值本质：返回值大于0的话，表示让o1往上排；返回值小于0，表示让o2往上排。
                // return o1 - o2; 如果返回值大于0，表示：让o1往上排，此时表示大的那个数o1往上排。
                // return o2 - o1; 如果返回值大于0，表示：让o1往上排，此时表示小的那个数o1往上排
                return o2 - o1;
            }
        });
        BinaryTrees.print(heap);
    }

    private static void test3() {
        Integer[] arr = {15, 52, 2, 90, 59, 68, 25, 5, 13, 69, 12, 81, 10, 96, 16, 51, 56, 20, 42};
        MinBinaryHeap<Integer> heap = new MinBinaryHeap<>(arr);
        BinaryTrees.print(heap);
    }

    private static void test2() {
        Integer[] arr = {15, 52, 2, 90, 59, 68, 25, 5, 13, 69, 12, 81, 10, 96, 16, 51, 56, 20, 42};
        MaxBinaryHeap<Integer> heap = new MaxBinaryHeap<>(arr);
        BinaryTrees.print(heap);
    }

    private static void test1() {
        MaxBinaryHeap<Integer> heap = new MaxBinaryHeap<>();
        heap.add(68);
        heap.add(72);
        heap.add(43);
        heap.add(50);
        heap.add(38);
        heap.add(90);
        heap.add(22);
        heap.add(98);
        heap.add(10);
//        BinaryTrees.print(heap);
        heap.remove();
        BinaryTrees.print(heap);
    }
}
